package com.chenken;

import java.util.Comparator;

/**
 * 平衡二叉搜索树
 *
 */
public class BBST<E> extends BST<E>{

	public BBST() {
		this(null);
	}
	
	public BBST(Comparator<E> Comparator) {
		super(Comparator);
	}
	
	/**
	 *  失衡节点grand向左旋转
	 * @param grand
	 */
	protected void rotateLeft(Node<E> grand) {
		Node<E> parent = grand.right;//因为是向左旋转,所以parent在grand的右子树
		
		Node<E> pLeftChild = parent.left;
		grand.right = pLeftChild;//grade的右子树指向parent的左子树
		parent.left = grand;//parent的左子树指向grand
		
		afterRotate(grand, parent, pLeftChild);
	}
	
	/**
	 * 失衡节点grand向右旋转
	 * @param grand
	 */
	protected void rotateRight(Node<E> grand) {
		Node<E> parent = grand.left;//因为是向右旋转,所以parent在grand的左子树
		
		Node<E> pRightChild = parent.right;
		grand.left = pRightChild;
		parent.right = grand;
		
		afterRotate(grand, parent, pRightChild);
	}
	
	/**
	 * 旋转之后的操作
	 * @param grand
	 * @param parent
	 * @param pRightChild
	 */
	protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> pRightChild) {
		//	更新parent的parent为grand的parent
		parent.parent = grand.parent;
		//	让grand的子节点指向parent
		if(grand.isLeftChild()) {
			grand.parent.left = parent;
		}else if(grand.isRightChild()) {
			grand.parent.right = parent;
		}else {
			root = parent;
		}
		//	更新pRightChild的parent
		if(pRightChild != null ) {
			pRightChild.parent = grand;
		}
		//	更新grand的parent
		grand.parent = parent;
	}

}
